home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Environments / SmallEiffel 0.3.3 / SmallEiffel PPC / lib_std / link_list.e < prev    next >
Encoding:
Text File  |  1996-06-13  |  2.3 KB  |  146 lines  |  [TEXT/EDIT]
  1. -- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C) 
  2. -- Dominique COLNET and Suzanne COLLIN -- colnet@loria.fr
  3. --
  4. class LINK_LIST[E]
  5. -- 
  6. -- One way linked list.
  7. --
  8.  
  9. inherit COLLECTION[E];
  10.  
  11. creation {ANY}
  12.    make, from_array
  13.  
  14. feature
  15.  
  16.    lower: INTEGER is 1;
  17.      -- Lower index bound.
  18.    
  19.    upper: INTEGER;
  20.      -- Upper index bound.
  21.  
  22. feature {NONE}
  23.    
  24.    first_link: LINK[E];
  25.  
  26.    last_i: INTEGER;
  27.      -- When greater than 0, the last access done memorized
  28.      -- in `last_link'.
  29.  
  30.    last_link: like first_link;
  31.    
  32. feature -- Creation and Modification :
  33.    
  34.    make is
  35.       do
  36.      first_link := Void;
  37.      upper := 0;
  38.      last_i := 0;
  39.       ensure
  40.      count = 0
  41.       end;
  42.  
  43.    from_array(a: ARRAY[E]) is
  44.       require
  45.      a /= Void
  46.       local
  47.      i: INTEGER;
  48.       do
  49.      if first_link = Void then
  50.         from
  51.            i := a.upper;
  52.         until
  53.            i < a.lower
  54.         loop
  55.            !!first_link.make(a.item(i),first_link);
  56.            i := i - 1;
  57.         end;
  58.         upper := a.upper;
  59.      else
  60.         not_yet_implemented;
  61.      end;
  62.      if a.count > 0 then
  63.         last_link := first_link;
  64.         last_i := 1;
  65.      else
  66.         last_link := Void;
  67.         last_i := 1;
  68.      end;
  69.       ensure
  70.      count = a.count
  71.       end;
  72.  
  73. feature -- Accessing :
  74.  
  75.    infix "@", item(index: INTEGER): E is
  76.       do
  77.      go_item(index);
  78.      Result := last_link.item;
  79.       end;
  80.    
  81. feature -- Modification :
  82.    
  83.    put(element: E; index: INTEGER) is
  84.       do
  85.      go_item(index);
  86.      last_link.set_item(element);
  87.       end;
  88.  
  89.    add_first(e: E) is
  90.       do
  91.      !!first_link.make(e,first_link);
  92.      upper := upper + 1;
  93.      last_i := 1;
  94.      last_link := first_link;
  95.       end;
  96.  
  97.    copy(other: like Current) is
  98.      -- Copy `other' onto Current.
  99.       local
  100.      i: INTEGER;
  101.       do
  102.      from
  103.         i := 1;
  104.         last_i := 1;
  105.         last_item := first_link;
  106.      until
  107.         i > other.upper
  108.      loop
  109.         not_yet_implemented;
  110.         put(other.item(i),i);
  111.         i := i - 1;
  112.      end;
  113.       end;
  114.  
  115. feature {NONE}
  116.  
  117.    go_item(i: INTEGER) is
  118.       require
  119.      valid_index(i)
  120.       do
  121.      if i = last_i then
  122.      else
  123.         if last_i > i then
  124.            last_i := 1;
  125.            last_link := first_link;
  126.         end;
  127.         from
  128.         until
  129.            i = last_i
  130.         loop
  131.            last_link := last_link.next;
  132.            last_i := last_i + 1;
  133.         end;
  134.      end;
  135.       ensure
  136.      last_i = i
  137.       end;
  138.  
  139. invariant
  140.  
  141.    upper = 0 implies first_link = Void;
  142.    
  143.    first_link = Void implies upper = 0;
  144.    
  145. end -- LINK_LIST[E]
  146.